Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра “Автоматизовані системи управління” / Лабораторна робота № 15 Задачі динамічного програмування з курсу “ Методи оптимізації дослідження операцій”  Теоретичні відомості Динамічне програмування — розділ математики, який присвячений теорії і методам розв'язання багатокрокових задач оптимального управління. У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «прийняття рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються. Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.) 1.1 Методика розв’язування динамічних задач Нехай потрібно оптимізувати деякий керований процес, перебіг якого можна розбити на послідовні етапи (кроки), що задаються. Ефективність усього процесу Z є сумою ефективностей Zj (
) окремих кроків:
(адитивний критерій) або
(мультиплікативний критерій). З кожним кроком задачі пов’язане прийняття певного рішення, так званого покрокового управління хj (
), що визначає як ефективність даного стану, так і всієї операції в цілому. У задачі динамічного програмування знаходять таке управління X = (x1, x2, …, xn) всією операцією, яке максимізує її загальну ефективність: Оптимальним розв’язком цієї задачі є управління Х* , що складається із сукупності оптимальних покрокових управлінь
і забезпечує максимальну ефективність Z* Усі типи задач динамічного програмування розв’язують, керуючись основним принципом: яким би не був стан системи S перед черговим кроком, управління на цьому кроці слід вибрати так, щоб ефективність розглядуваного кроку в сумі з оптимальною ефективністю на всіх наступних кроках були максимальними (принцип Беллмана). Отже, маємо наступний алгоритм розв’язування задач динамічного програмування: Визначаємо специфіку стану заданої керованої системи та множини параметрів, які описують цей стан. Стан системи обираємо таким чином, щоб забезпечити зв’язок між послідовними етапами перебігу процесу та знайти допустимий розв’язок задачі в цілому як результат оптимізації на кожному кроці зокрема. При цьому оптимальні розв’язки на наступних етапах приймаємо, нехтуючи впливом наступних рішень на прийняті раніше. Поділяємо динамічний процес на етапи (кроки), що відповідають, як правило, часовим періодам планування чи окремим об’єктам (підприємствам, видам продукції, устаткування тощо), стосовно яких розробляються управлінські рішення. Формуємо перелік управлінських рішень xj (
) для кожного кроку та відповідні обмеження щодо них. Визначаємо ефект, який забезпечується управлінським рішенням xj на j-му кроці, якщо перед тим система була в стані S:
. Досліджуємо, як змінюється стан S системи під впливом управлінського рішення xj на j-му кроці: Для розглядуваної задачі будуємо рекурентну залежність, яка визначає умовний оптимальний ефект Zj(s), починаючи з j-го кроку і до останнього, через уже відому функцію Zj+1(s’): Цьому ефекту відповідає умовне оптимальне управління на j-му кроці (xj(s)). Зауважимо, що за аргумент функції Zj+1(s) беремо не s, а змінений с...